<html>
<head><meta charset="utf-8"><title>copying undef optimization #58556 · t-compiler/const-eval · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/146212-t-compiler/const-eval/index.html">t-compiler/const-eval</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/146212-t-compiler/const-eval/topic/copying.20undef.20optimization.20.2358556.html">copying undef optimization #58556</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="160567247"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/146212-t-compiler/const-eval/topic/copying%20undef%20optimization%20%2358556/near/160567247" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> pnkfelix <a href="https://rust-lang.github.io/zulip_archive/stream/146212-t-compiler/const-eval/topic/copying.20undef.20optimization.20.2358556.html#160567247">(Mar 12 2019 at 12:57)</a>:</h4>
<p>hi <span class="user-mention" data-user-id="124288">@oli</span></p>



<a name="160567259"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/146212-t-compiler/const-eval/topic/copying%20undef%20optimization%20%2358556/near/160567259" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> pnkfelix <a href="https://rust-lang.github.io/zulip_archive/stream/146212-t-compiler/const-eval/topic/copying.20undef.20optimization.20.2358556.html#160567259">(Mar 12 2019 at 12:58)</a>:</h4>
<p>I wanted to double check something with you about this PR</p>



<a name="160567325"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/146212-t-compiler/const-eval/topic/copying%20undef%20optimization%20%2358556/near/160567325" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> pnkfelix <a href="https://rust-lang.github.io/zulip_archive/stream/146212-t-compiler/const-eval/topic/copying.20undef.20optimization.20.2358556.html#160567325">(Mar 12 2019 at 12:58)</a>:</h4>
<p>namely I wanted to understand the purpose of making the so-called "precomputed cache" <a href="https://github.com/rust-lang/rust/pull/58556/files#diff-303d6ab00ef20008541e8be51d727234R794" target="_blank" title="https://github.com/rust-lang/rust/pull/58556/files#diff-303d6ab00ef20008541e8be51d727234R794">here</a></p>



<a name="160567340"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/146212-t-compiler/const-eval/topic/copying%20undef%20optimization%20%2358556/near/160567340" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> pnkfelix <a href="https://rust-lang.github.io/zulip_archive/stream/146212-t-compiler/const-eval/topic/copying.20undef.20optimization.20.2358556.html#160567340">(Mar 12 2019 at 12:58)</a>:</h4>
<p>which I <em>think</em> is an attempt to make a compressed form of the input bitvector</p>



<a name="160567368"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/146212-t-compiler/const-eval/topic/copying%20undef%20optimization%20%2358556/near/160567368" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> pnkfelix <a href="https://rust-lang.github.io/zulip_archive/stream/146212-t-compiler/const-eval/topic/copying.20undef.20optimization.20.2358556.html#160567368">(Mar 12 2019 at 12:59)</a>:</h4>
<p>and then, if the result of the compression is actually trivial (i.e. we found out it was all zeros or all one bits), we sidestep the copy entirely</p>



<a name="160567381"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/146212-t-compiler/const-eval/topic/copying%20undef%20optimization%20%2358556/near/160567381" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> pnkfelix <a href="https://rust-lang.github.io/zulip_archive/stream/146212-t-compiler/const-eval/topic/copying.20undef.20optimization.20.2358556.html#160567381">(Mar 12 2019 at 12:59)</a>:</h4>
<p>and otherwise, I <em>think</em> we subsequently "decompress" the compressed form into the target buffer</p>



<a name="160567497"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/146212-t-compiler/const-eval/topic/copying%20undef%20optimization%20%2358556/near/160567497" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> pnkfelix <a href="https://rust-lang.github.io/zulip_archive/stream/146212-t-compiler/const-eval/topic/copying.20undef.20optimization.20.2358556.html#160567497">(Mar 12 2019 at 13:01)</a>:</h4>
<p>If the above interpretation is correct, then the main (and only?) benefit I can imagine is that you can fit more of the input buffer into your processor cache during the reading, and likewise during the subsequent writing</p>



<a name="160567515"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/146212-t-compiler/const-eval/topic/copying%20undef%20optimization%20%2358556/near/160567515" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> pnkfelix <a href="https://rust-lang.github.io/zulip_archive/stream/146212-t-compiler/const-eval/topic/copying.20undef.20optimization.20.2358556.html#160567515">(Mar 12 2019 at 13:01)</a>:</h4>
<p>rather than trying to dedicate half of your cache and the other half of the cache to the other if you were to do a more direct copy</p>



<a name="160567573"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/146212-t-compiler/const-eval/topic/copying%20undef%20optimization%20%2358556/near/160567573" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> pnkfelix <a href="https://rust-lang.github.io/zulip_archive/stream/146212-t-compiler/const-eval/topic/copying.20undef.20optimization.20.2358556.html#160567573">(Mar 12 2019 at 13:02)</a>:</h4>
<p>(this is all assuming that one <em>could</em> just have added a prepass to the original code just look if its all zeros or all ones, and skip the copy if that is the case.)</p>



<a name="160567590"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/146212-t-compiler/const-eval/topic/copying%20undef%20optimization%20%2358556/near/160567590" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> pnkfelix <a href="https://rust-lang.github.io/zulip_archive/stream/146212-t-compiler/const-eval/topic/copying.20undef.20optimization.20.2358556.html#160567590">(Mar 12 2019 at 13:02)</a>:</h4>
<p>(of course the cost/benefit of such a second pass is hard for me to determine)</p>



<a name="160570028"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/146212-t-compiler/const-eval/topic/copying%20undef%20optimization%20%2358556/near/160570028" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> oli <a href="https://rust-lang.github.io/zulip_archive/stream/146212-t-compiler/const-eval/topic/copying.20undef.20optimization.20.2358556.html#160570028">(Mar 12 2019 at 13:35)</a>:</h4>
<p>It's both a processor cache thing, and a way to get around the problem, that iterating over bits and setting them one by one in a big integer is super slow</p>



<a name="160570108"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/146212-t-compiler/const-eval/topic/copying%20undef%20optimization%20%2358556/near/160570108" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> oli <a href="https://rust-lang.github.io/zulip_archive/stream/146212-t-compiler/const-eval/topic/copying.20undef.20optimization.20.2358556.html#160570108">(Mar 12 2019 at 13:36)</a>:</h4>
<p>the <code>set_range_inbounds</code> method is optimized to do two bitshifts and a bitmask instead of iterating over all the bits</p>



<a name="160571234"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/146212-t-compiler/const-eval/topic/copying%20undef%20optimization%20%2358556/near/160571234" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> oli <a href="https://rust-lang.github.io/zulip_archive/stream/146212-t-compiler/const-eval/topic/copying.20undef.20optimization.20.2358556.html#160571234">(Mar 12 2019 at 13:49)</a>:</h4>
<p>So the reason I am not just computing this while copying is that we are copying a single value <code>repeat</code> times. This means that we'd be recomputing them <code>repeat</code> times if we just did it while copying</p>



<a name="160571279"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/146212-t-compiler/const-eval/topic/copying%20undef%20optimization%20%2358556/near/160571279" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> oli <a href="https://rust-lang.github.io/zulip_archive/stream/146212-t-compiler/const-eval/topic/copying.20undef.20optimization.20.2358556.html#160571279">(Mar 12 2019 at 13:50)</a>:</h4>
<p>The cache only computes the set once and then reuses it for all duplicates (or if the entire thing is homogenous, just does a single operation).</p>



<a name="160571395"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/146212-t-compiler/const-eval/topic/copying%20undef%20optimization%20%2358556/near/160571395" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> oli <a href="https://rust-lang.github.io/zulip_archive/stream/146212-t-compiler/const-eval/topic/copying.20undef.20optimization.20.2358556.html#160571395">(Mar 12 2019 at 13:50)</a>:</h4>
<p>We could even go as far as figuring out that as long as the sequence length is a divisor of 64, we can just fill in a <code>u64</code> once and copy that one</p>



<a name="160574761"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/146212-t-compiler/const-eval/topic/copying%20undef%20optimization%20%2358556/near/160574761" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> pnkfelix <a href="https://rust-lang.github.io/zulip_archive/stream/146212-t-compiler/const-eval/topic/copying.20undef.20optimization.20.2358556.html#160574761">(Mar 12 2019 at 14:29)</a>:</h4>
<p>I guess my point is, I can imagine some input buffers where the "compressed form" is not efficient at all</p>



<a name="160574864"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/146212-t-compiler/const-eval/topic/copying%20undef%20optimization%20%2358556/near/160574864" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> pnkfelix <a href="https://rust-lang.github.io/zulip_archive/stream/146212-t-compiler/const-eval/topic/copying.20undef.20optimization.20.2358556.html#160574864">(Mar 12 2019 at 14:30)</a>:</h4>
<p>i.e. if you had an input buffer 01010101... then you almost certainly would have been better off with the original code (right?)</p>



<a name="160574980"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/146212-t-compiler/const-eval/topic/copying%20undef%20optimization%20%2358556/near/160574980" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> oli <a href="https://rust-lang.github.io/zulip_archive/stream/146212-t-compiler/const-eval/topic/copying.20undef.20optimization.20.2358556.html#160574980">(Mar 12 2019 at 14:31)</a>:</h4>
<p>oh yea</p>



<a name="160574982"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/146212-t-compiler/const-eval/topic/copying%20undef%20optimization%20%2358556/near/160574982" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> oli <a href="https://rust-lang.github.io/zulip_archive/stream/146212-t-compiler/const-eval/topic/copying.20undef.20optimization.20.2358556.html#160574982">(Mar 12 2019 at 14:31)</a>:</h4>
<p>hmm</p>



<a name="160574983"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/146212-t-compiler/const-eval/topic/copying%20undef%20optimization%20%2358556/near/160574983" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> pnkfelix <a href="https://rust-lang.github.io/zulip_archive/stream/146212-t-compiler/const-eval/topic/copying.20undef.20optimization.20.2358556.html#160574983">(Mar 12 2019 at 14:31)</a>:</h4>
<p>but I'm also willing to believe that in practice, you <strong>are</strong> seeing long ranges with the same value (0 or 1) repeated, and thus the run-length encoded <code>ranges</code> will be very compact and very fast to decompress into each of the <code>dest_allocation</code>s</p>



<a name="160575026"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/146212-t-compiler/const-eval/topic/copying%20undef%20optimization%20%2358556/near/160575026" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> oli <a href="https://rust-lang.github.io/zulip_archive/stream/146212-t-compiler/const-eval/topic/copying.20undef.20optimization.20.2358556.html#160575026">(Mar 12 2019 at 14:32)</a>:</h4>
<p>we could detect such cases and just resort to the original code?</p>



<a name="160575058"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/146212-t-compiler/const-eval/topic/copying%20undef%20optimization%20%2358556/near/160575058" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> pnkfelix <a href="https://rust-lang.github.io/zulip_archive/stream/146212-t-compiler/const-eval/topic/copying.20undef.20optimization.20.2358556.html#160575058">(Mar 12 2019 at 14:32)</a>:</h4>
<p>or at least, I am assuming that you saw long ranges with the same value arise  in practice, right?</p>



<a name="160575071"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/146212-t-compiler/const-eval/topic/copying%20undef%20optimization%20%2358556/near/160575071" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> oli <a href="https://rust-lang.github.io/zulip_archive/stream/146212-t-compiler/const-eval/topic/copying.20undef.20optimization.20.2358556.html#160575071">(Mar 12 2019 at 14:32)</a>:</h4>
<p>oh yea, mostly it's all bits defined</p>



<a name="160575080"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/146212-t-compiler/const-eval/topic/copying%20undef%20optimization%20%2358556/near/160575080" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> pnkfelix <a href="https://rust-lang.github.io/zulip_archive/stream/146212-t-compiler/const-eval/topic/copying.20undef.20optimization.20.2358556.html#160575080">(Mar 12 2019 at 14:32)</a>:</h4>
<p>okay. Then I'll just r+ this. <span aria-label="smiley" class="emoji emoji-1f603" role="img" title="smiley">:smiley:</span></p>



<a name="160575097"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/146212-t-compiler/const-eval/topic/copying%20undef%20optimization%20%2358556/near/160575097" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> oli <a href="https://rust-lang.github.io/zulip_archive/stream/146212-t-compiler/const-eval/topic/copying.20undef.20optimization.20.2358556.html#160575097">(Mar 12 2019 at 14:32)</a>:</h4>
<p>hehe ok</p>



<a name="160575120"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/146212-t-compiler/const-eval/topic/copying%20undef%20optimization%20%2358556/near/160575120" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> oli <a href="https://rust-lang.github.io/zulip_archive/stream/146212-t-compiler/const-eval/topic/copying.20undef.20optimization.20.2358556.html#160575120">(Mar 12 2019 at 14:33)</a>:</h4>
<p>I can revisit for more perf improvements if new cases come up</p>



<a name="160575162"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/146212-t-compiler/const-eval/topic/copying%20undef%20optimization%20%2358556/near/160575162" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> pnkfelix <a href="https://rust-lang.github.io/zulip_archive/stream/146212-t-compiler/const-eval/topic/copying.20undef.20optimization.20.2358556.html#160575162">(Mar 12 2019 at 14:33)</a>:</h4>
<p>I will admit that I overlooked the fact that you are repetitively writing the output <code>repeat</code> times</p>



<a name="160575241"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/146212-t-compiler/const-eval/topic/copying%20undef%20optimization%20%2358556/near/160575241" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> pnkfelix <a href="https://rust-lang.github.io/zulip_archive/stream/146212-t-compiler/const-eval/topic/copying.20undef.20optimization.20.2358556.html#160575241">(Mar 12 2019 at 14:34)</a>:</h4>
<p>I only noticed a single copy and so was not convinced it was worth making the run-length encoded form. But if you are generating multiple copies,  I can believe it ends up paying off.</p>



<a name="160575662"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/146212-t-compiler/const-eval/topic/copying%20undef%20optimization%20%2358556/near/160575662" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> pnkfelix <a href="https://rust-lang.github.io/zulip_archive/stream/146212-t-compiler/const-eval/topic/copying.20undef.20optimization.20.2358556.html#160575662">(Mar 12 2019 at 14:39)</a>:</h4>
<p>(Actually, it would probably be really easy to add logic saying "if <code>ranges</code> is larger than <code>undef_mask</code>, then just use <code>undef_mask</code> as the source rather than spending time decompressing <code>ranges</code>, right?)</p>



<a name="160575681"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/146212-t-compiler/const-eval/topic/copying%20undef%20optimization%20%2358556/near/160575681" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> pnkfelix <a href="https://rust-lang.github.io/zulip_archive/stream/146212-t-compiler/const-eval/topic/copying.20undef.20optimization.20.2358556.html#160575681">(Mar 12 2019 at 14:39)</a>:</h4>
<p>Just something to consider. It doesn't need to be part of this PR</p>



<a name="160575761"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/146212-t-compiler/const-eval/topic/copying%20undef%20optimization%20%2358556/near/160575761" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> pnkfelix <a href="https://rust-lang.github.io/zulip_archive/stream/146212-t-compiler/const-eval/topic/copying.20undef.20optimization.20.2358556.html#160575761">(Mar 12 2019 at 14:40)</a>:</h4>
<p>(I'm basically just repeating what you said above when you said "we could detect such cases and just resort to the original code"; i just hadn't realized how trivially we might detect such cases.)</p>



<a name="160604862"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/146212-t-compiler/const-eval/topic/copying%20undef%20optimization%20%2358556/near/160604862" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> RalfJ <a href="https://rust-lang.github.io/zulip_archive/stream/146212-t-compiler/const-eval/topic/copying.20undef.20optimization.20.2358556.html#160604862">(Mar 12 2019 at 20:02)</a>:</h4>
<blockquote>
<p>oh yea, mostly it's all bits defined</p>
</blockquote>
<p>well, except for padding</p>



<a name="160605667"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/146212-t-compiler/const-eval/topic/copying%20undef%20optimization%20%2358556/near/160605667" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jake Goulding <a href="https://rust-lang.github.io/zulip_archive/stream/146212-t-compiler/const-eval/topic/copying.20undef.20optimization.20.2358556.html#160605667">(Mar 12 2019 at 20:13)</a>:</h4>
<p>What's a little padding between friends?</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>